10.3 幾個簡單的 Leetcode 例題

如果邊的權重都相等，那麼使用 BFS 就可以為我們找出最短的路徑了。
今天來講講簡單的最短路徑例題吧。
這幾個例子都是透過建構一張圖，並且在上面計算最短路徑。

Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

題目大意：給你一個 M * N 的格點，你想要從左上角的 (0, 0) 走到右下角的 (m-1, n-1)。格子內若標記為 1 代表有障礙物，標記為 0 則為空地。若只能消除不超過 K 個障礙物，請問至少得走幾步才能從左上走到右下呢？

解題想法：我們可以將 "消除了多少障礙物" 這個條件加入圖中。將每一個格子與目前已消除的障礙物數量當作一個圖上的節點 (k, x, y)，若相鄰的格子 (x’, y’) 有障礙物，則建立一條邊連至 (k+1, x’, y’)，否則連至 (k, x’, y’)。最終求得 (0, 0, 0) 走到 min_{k’<=k}{ (k’, m-1, n-1) } 的最短路徑。
時間複雜度是 O(kmn)，空間也需要 O(kmn)。

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int dist[1605][50][50];
        memset(dist, -1, sizeof(dist));
        
        queue<int> Q;
        Q.push(0); Q.push(0); Q.push(0); dist[0][0][0] = 0;
        while (!Q.empty()) {
            int l = Q.front(); Q.pop();
            int x = Q.front(); Q.pop();
            int y = Q.front(); Q.pop();
            int dx[4] = {-1, 0, 1, 0};
            int dy[4] = {0, 1, 0, -1};
            if (x == m-1 && y == n-1) return dist[l][x][y];
            for (int f = 0; f < 4; f++) {
                int nx = x + dx[f];
                int ny = y + dy[f];
                if (nx>=0 && nx<m && ny>=0 && ny<n) {
                    if (l < k && grid[nx][ny] == 1 && dist[l+1][nx][ny] == -1) {
                        dist[l+1][nx][ny] = dist[l][x][y] + 1;
                        Q.push(l+1); Q.push(nx); Q.push(ny);
                    } else if (grid[nx][ny] == 0 && dist[l][nx][ny] == -1) {
                        dist[l][nx][ny] = dist[l][x][y] + 1;
                        Q.push(l); Q.push(nx); Q.push(ny);
                    }
                }
            }
        }
        return -1;
    }
};

Leetcode 1368. Minimum Cost to Make At Least One Valid Path in a Grid

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

題目大意：給你一個 M * N 的格子點，每一格上面有個箭頭。你想要從 (0, 0) 走到 (m-1, n-1)，但是你只能順著箭頭方向前進。你的目標是將最少數量的格子內的箭頭變換方向，使得你能夠走完整條路徑。求最少的箭頭改變次數。

解題想法：這題跟前一題很像，但不太一樣。我們只需要對每一個格子建立一個點，但是格子與格子之間的邊，可能是免費、可能要花 1 單位的花費，所以是有權重的。在這種邊權重僅僅是 0 或 1 的特殊情形下，我們仍然可以用類似 BFS 的方式來找出答案：優先處理邊權重是 0 的那些格子。

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int dist[105][105];
        memset(dist, -1, sizeof(dist));
        deque<pair<int, int>> Q;
        Q.push_back({0, 0});
        dist[0][0] = 0;
        while (!Q.empty()) {
            auto p = Q.front(); Q.pop_front();
            int x = p.first;
            int y = p.second;
            const int dx[4] = {0, 0, 1, -1};
            const int dy[4] = {1, -1, 0, 0};
            for(int f = 0; f < 4; f++) {
                int nx = x + dx[f];
                int ny = y + dy[f];
                if (nx>=0 && nx<m && ny>=0 && ny<n) {
                    if (grid[x][y] == f+1 && (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y])) {
                        dist[nx][ny] = dist[x][y];
                        Q.push_front({nx, ny});
                    } else if (grid[x][y] != f+1 && (dist[nx][ny] == -1 || dist[nx][ny] > dist[x][y] + 1)) {
                        dist[nx][ny] = dist[x][y] + 1;
                        Q.push_back({nx, ny});
                    }
                }
            }
        }
        
        return dist[m-1][n-1];
    }
};